package ink.tsg.javabase.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author dzsg
 * @Description 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如，给出
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 * 返回如下的二叉树：
 *            3
 *         /   \
 *        9    20
 *            /  \
 *          15   7
 * @Date 2020/11/4 10:29
 **/
public class BuildTree {

    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7}; //前序遍历
        int[] inorder = {9, 3, 15, 20, 7};  //中序遍历
        TreeNode treeNode = buildTree(preorder, inorder);


    }
    /*
     *
     **/
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0||inorder.length==0){
            return null;
        }
        HashMap<Integer, Integer> inorderMap = new HashMap<>();
        int length = inorder.length;
        for(int i=0;i<length;i++){
            inorderMap.put(inorder[i],i);
        }
        TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, inorderMap);
        return root;
    }

    private static TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
        if (preorderStart > preorderEnd) {
            return null;
        }
        // 前序遍历的第一个是树的根节点
        int rootVal = preorder[preorderStart];
        TreeNode root = new TreeNode(rootVal);

        if (preorderStart == preorderEnd) {
            return root;
        } else {
            // 得到根节点的下标
            int rootIndex = indexMap.get(rootVal);

            int leftNodes = rootIndex - inorderStart, rightNodes = inorderEnd - rootIndex;
            TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes, inorder, inorderStart, rootIndex - 1, indexMap);
            TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
            root.left = leftSubtree;
            root.right = rightSubtree;
            return root;
        }

    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}